package 力扣._100048_美丽塔2;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public long maximumSumOfHeights(List<Integer> maxHeights) {
        //
        //向左求和，向右求和
        long[] left = new long[maxHeights.size()];
        long[] right = new long[maxHeights.size()];
        left[0] = maxHeights.get(0);
        right[0] = maxHeights.get(maxHeights.size() - 1);
        for (int i = 1; i < maxHeights.size(); i++) {
            int last = maxHeights.get(i);
            left[i] = last;
            for (int j = i - 1; j >= 0; j--) {
                if (maxHeights.get(j) <= last) {
                    left[i] += left[j];
                    break;
                } else {
                    left[i] += last;
                }
            }
        }
        for (int i = maxHeights.size() - 1; i >= 0; i--) {
            int last = maxHeights.get(i);
            right[i] = last;
            for (int j = i + 1; j < maxHeights.size(); j++) {
                if (maxHeights.get(j) <= last) {
                    right[i] += right[j];
                    break;
                } else {
                    right[i] += last;
                }
            }
        }
        long max = left[0] + right[0] - maxHeights.get(0);
        for (int i = 1; i < left.length; i++)
            max = Math.max(max, left[i] + right[i] - maxHeights.get(i));
        return max;
    }

    public static void main(String[] args) {
        List<Integer> list  =new ArrayList<>();
        list.add(5);
        list.add(3);
        list.add(4);
        list.add(1);
        list.add(1);
        long l = new Solution().maximumSumOfHeights(list);
        System.out.println(l);

    }
}
